/*ver 0.1 made by Jeroen S and W 
 * implemented methods of interface Build
 * ver 0.2 - 02-01-2008 - by Jeroen S
 * Minor bugfixes and other cleanup
 * ver 0.3 - 02-01-2008 - by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 *  ver: 0.4, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 * 
 *   ver:0.5 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 * 
 * 
 */

package mazeAssignment;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;

/**
 * Implements the Prim-based maze building algorithm.
 * Utilizing a HashSet for visited items and a binary-search-tree for unvisited items.
 * @author Marcel Hekman
 */
public class PathBuildBinaryTree implements Build{

	private Maze mazeGrid;
	private Random randomGen;
	private HashSet<Integer> visited;
	private BinaryTree<Integer> notVisited;
	
	private int mazeSize;
	
	
	@Override
	public Maze getMaze()
	{
		return mazeGrid;
	}
	
	@Override
	public boolean isDone()
	{
		return notVisited.isEmpty();
	}
	
	@Override
	public void initialise(Maze maze)
	{
		this.mazeGrid = maze;
		this.mazeSize = mazeGrid.getSizeX() * mazeGrid.getSizeY();
		
		this.randomGen = new Random( System.currentTimeMillis() );
		this.visited = new HashSet<Integer>(mazeSize, 1.1f);
		this.notVisited = new BinaryTree<Integer>();
		
		//Set start and end
		MazeElement start = mazeGrid.getElement(0, 0);
		start.setSolveState(MazeElement.SOLVE_START);
		MazeElement end = mazeGrid.getElement(mazeGrid.getSizeX()-1, mazeGrid.getSizeY()-1);
		end.setSolveState(MazeElement.SOLVE_END);
		
		//Pick first cell
		int firstCell = this.randomGen.nextInt( this.mazeSize );
		
		this.notVisited.add(firstCell);
		processNode( firstCell, true );
	}
	
	@Override
	public boolean tick()
	{
		if(isDone())
			return false;
		
		//Randomly select a node from the notVisited data-structure.
		int randomNode = randomGen.nextInt( notVisited.size() );
		
		processNode( notVisited.get( randomNode ), false );
		
		return true;
	}
	
	
	private void processNode(int nodeNumber, boolean firstRun)
	{
		int sizeX = mazeGrid.getSizeX();
		int sizeY = mazeGrid.getSizeY();
		
		int posX = nodeNumber % sizeX;
		int posY = nodeNumber / sizeX;
		
		
		//Calculate the possible directions to connect back to current maze
		//And add all unvisited nodes to the unvisited data structure.
		ArrayList<Integer> possibleX = new ArrayList<Integer>(4);
		ArrayList<Integer> possibleY = new ArrayList<Integer>(4);
		MazeElement current = mazeGrid.getElement(posX, posY);
		
		//North
		if(posY > 0 && current.getNorth())
		{
			if(visited.contains((Integer)nodeNumber-sizeX))
			{
				possibleX.add(posX);
				possibleY.add(posY-1);
			}
			else if(! notVisited.contains(nodeNumber-sizeX))
				notVisited.add(nodeNumber-sizeX);
		}
		//South
		if(posY < (sizeY-1) && current.getSouth())
		{
			if(visited.contains((Integer)nodeNumber+sizeX))
			{
				possibleX.add(posX);
				possibleY.add(posY+1);
			}
			else if(! notVisited.contains(nodeNumber+sizeX))
				notVisited.add(nodeNumber+sizeX);
		}
		//East
		if(posX > 0 && current.getEast())
		{
			if(visited.contains((Integer)nodeNumber-1))
			{
				possibleX.add(posX-1);
				possibleY.add(posY);
			}
			else if(! notVisited.contains(nodeNumber-1))
				notVisited.add(nodeNumber-1);
		}
		//West
		if(posX < (sizeX-1) && current.getWest())
		{
			if(visited.contains((Integer)nodeNumber+1))
			{
				possibleX.add(posX+1);
				possibleY.add(posY);
			}
			else if(! notVisited.contains(nodeNumber+1))
				notVisited.add(nodeNumber+1);
		}
		
		//Only skipped during first run
		if(!firstRun)
		{
			if(possibleX.isEmpty())
				throw new RuntimeException();
			
			
			//Connect to the maze
			int selectedCell = randomGen.nextInt( possibleX.size() );
			int selectedX = possibleX.get( selectedCell );
			int selectedY = possibleY.get( selectedCell );
			MazeElement selectedElement = mazeGrid.getElement(selectedX, selectedY);
			
			//North or south
			if(posX == selectedX)
			{
				if(posY < selectedY)
				{
					current.setSouth(false);
					selectedElement.setNorth(false);
				}
				else
				{
					current.setNorth(false);
					selectedElement.setSouth(false);
				}
			}
			//East or west
			else
			{
				if(posX < selectedX)
				{
					current.setEast(false);
					selectedElement.setWest(false);
				}
				else
				{
					current.setWest(false);
					selectedElement.setEast(false);
				}
			}
		}
		
		visited.add( nodeNumber );
		notVisited.remove( nodeNumber );
	}
}
